//给定一个二叉树，返回它的 后序 遍历。 
//
// 示例: 
//
// 输入: [1,null,2,3]  
//   1
//    \
//     2
//    /
//   3 
//
//输出: [3,2,1] 
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
// Related Topics 栈 树 深度优先搜索 二叉树 
// 👍 701 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class BinaryTreePostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new BinaryTreePostorderTraversal().new Solution();
    }
    public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        suffixList(root);
        return res;

    }

    public void suffixOrder(TreeNode root){
        if (root == null) return;
        suffixOrder(root.left);
        suffixOrder(root.right);
        res.add(root.val);
    }

    /**
     * 使用迭代的方式进行后续遍历的话，可以使用链表来实现，
     * 当前节点不为空则插入元素，插入时使用头插法，左子节点不为空就入栈，然后当前节点指向右子节点进行循环
     * 如果当前节点为空的话就出栈
     *
     * 这样使用头插法的话最终顺序就是后续遍历了
     * 整个过程相当于是反着进行的，根 右 左
     *
     * 另一种方法，修改前序遍历的迭代法，前序遍历为 中->左->右，可以改为中->右->左 的方式遍历存储
     * 返回时反转一下就行了，这样明显会慢很多
     */
    public List<Integer> suffixList(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        /*stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left!=null) stack.add(node.left);//先入会后添加左，最终顺序为中 右 左，再进行反转
            if (node.right!=null) stack.add(node.right);
        }
        Collections.reverse(res);
        return res;*/
         LinkedList<Integer> list = new LinkedList<>();
        while (!stack.isEmpty() || root!=null){
            if (root!=null){
                list.addFirst(root.val);//TODO 头插法添加元素
                if (root.left!=null) stack.push(root.left);//最后访问左子节点
                root = root.right;//先访问右子节点
            }else root = stack.pop();
        }
        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
























